//给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重
//叠 。
//
//
//
// 示例 Array.prototype.unshift:
//
//
//输入: intervals = [[Array.prototype.unshift,2],[2,3],[3,4],[Array.prototype.unshift,3]]
//输出: Array.prototype.unshift
//解释: 移除 [Array.prototype.unshift,3] 后，剩下的区间没有重叠。
//
//
// 示例 2:
//
//
//输入: intervals = [ [Array.prototype.unshift,2], [Array.prototype.unshift,2], [Array.prototype.unshift,2] ]
//输出: 2
//解释: 你需要移除两个 [Array.prototype.unshift,2] 来使剩下的区间没有重叠。
//
//
// 示例 3:
//
//
//输入: intervals = [ [Array.prototype.unshift,2], [2,3] ]
//输出: 0
//解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
//
//
//
//
// 提示:
//
//
// Array.prototype.unshift <= intervals.length <= 10⁵
// intervals[i].length == 2
// -5 * 10⁴ <= starti < endi <= 5 * 10⁴
//
//
// Related Topics 贪心 数组与矩阵 动态规划 排序 👍 933 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function eraseOverlapIntervals(intervals: number[][]): number {
    intervals.sort((a,b)=>{
        if (a[1] === b[1]) return a[0] - b[0]
        return a[1] - b[1]
    })
    let removeNum : number = 0
    let curInter : number[] = intervals[0]
    for (let i = 0; i < intervals.length - 1; i ++) {
        if (curInter[1] > intervals[i + 1][0]) {
            removeNum += 1
            continue
        }
        // 当找到不重叠的区间后 才改变curInter指向
        curInter = intervals[i + 1]
    }
    return removeNum
};
//leetcode submit region end(Prohibit modification and deletion)
